package com.tried.kind.algorithm.sort;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSort {

    /**
     * 希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
     * 将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
     *
     * 2、算法描述
     * ①. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
     * ②. 按增量序列个数k，对序列进行k 趟排序；
     * ③. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时
     * ，整个序列作为一个表来处理，表长度即为整个序列的长度。
     *
     * 希尔排序复杂度:
     *
     * 平均时间复杂度	最好情况	最坏情况	空间复杂度
     * O(nlog2 n)	O(nlog2 n)	O(nlog2 n)	O(1)
     *
     *  官方版 grap取值较好
     * @param args
     */
    public static void main(String[] args) {
        int[] arry = {5,9,3,4,79,46,89,26,75,8,7,1,55,234,567,234,67,78,34,32};
        int grap = arry.length / 2;
        for (;grap >0; grap /= 2){
            for (int i = 0; (i+grap) < arry.length; i++){
                for (int k = 0; (k+grap) < arry.length; k+=grap){
                    if (arry[k] > arry[k+grap]){  // 升序
                        int temp = arry[k];
                        arry[k] = arry[k+grap];
                        arry[k+grap] = temp;
                        System.out.println("排序："+Arrays.toString(arry));
                    }
                }
            }
        }
    }


    /**
     * 希尔排序（Wiki官方版）
     *
     * 1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（注意此算法的gap取值）
     * 2. 按增量序列个数k，对序列进行k 趟排序；
     * 3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。
     *    仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
     * @param arr  待排序数组
     */
    public static void shell_sort(int[] arr) {
        int gap = 1, i, j, len = arr.length;
        int temp;
        while (gap < len / 3)
            gap = gap * 3 + 1;      // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...
        for (; gap > 0; gap /= 3) {
            for (i = gap; i < len; i++) {
                temp = arr[i];
                for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                    arr[j + gap] = arr[j];
                arr[j + gap] = temp;
            }
        }
    }
}
